import java.util.Stack;

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root == null){
            return false;
        }
        stack.push(root);
        if(root == node){
            return true;
        }

        boolean flag = getPath(root.left,node,stack);
        if(flag){
            return true;
        }

        flag = getPath(root.right,node,stack);
        if(flag){
            return true;
        }

        stack.pop();
        return false;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return null;
        }

        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();

        getPath(root,p,stack1);
        getPath(root,q,stack2);

        int len1 = stack1.size();
        int len2 = stack2.size();

        int len = len1 - len2;

        if(len < 0){
            len = Math.abs(len);
            while(len != 0){
                stack2.pop();
                len--;
            }
        }else{
            while(len != 0){
                stack1.pop();
                len--;
            }
        }

        //保证两个栈的长度一样
        while (!stack1.isEmpty() && !stack2.isEmpty()){
            if(stack1.peek() == stack2.peek()){
                return stack1.pop();
            }else{
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }
}